/* A library of methods for the Array object
 *
 * Copyright (c) 2009 Seth Wessitsh (seth@wessitsh.com)
 * Licensed under the MIT (MIT-LICENSE.txt) licence.
 */

if (typeof(Array.copy) == "undefined") {
	/**
		@interface {
			description: "
					Create a deep copy of the `arr' argument.

					Note: this function cannot handle circularly referenced arrays/objects. ",

			parameters: [
				{name: "arr", type: "array",
					description: "An array to create a copy of." } ]

			returns: { type: "array",
				description: "A deep copy of the input array." }
		}
	*/
	Array.copy = function(arr) {
		var oArr = [];

		for (var i=0; i < arr.length; i++) {
			switch(Object.typeName(arr[i])) {
				case "array":
					oArr[i] = Array.copy(arr[i]);
				break;
				case "object":
					oArr[i] = Object.copy(arr[i]);
				break;
				default:
					oArr[i] = arr[i];
			}
		}

		return oArr;
	};
} else {
	throw new Error("Static method Array.copy already exists.");
}

if (typeof(Array.except) == "undefined") {
	/**
		@interface {
			description: 
				"Create a new object with only the properties which occur in `a' but not in `b', and
				therefore, retaining the values in `a'.",

			parameters: [
				{name: "a", type: "object",
					description: 
						"An object whos properties will be added to the output object so long as
						they do not occur in `b'" },

				{name: "b", type: "object",
					description: 
						"An object whos properties will be used to mask off the 
						properties of `a'" } ]

			returns: { type: "object",
				description: 
					"A new object with all properties in `a' which do not occur in `b', and 
					therefore, retain the values in `a'." }
		}
	*/
	Array.except = function except(a,b) {
		var aIsArr = a instanceof Array, bIsArr = b instanceof Array, i;

		if (!aIsArr && !bIsArr) { return a === b ? [] : [a]; }
		if (!aIsArr) { a = [a]; }
		if (!bIsArr) { b = [b]; }

		var unique = {}, seen = {}, bitStrs = [],
			output = [], power = 0, num;

		bitStrs[0] = 0;
		bitStrs[1] = 0;

		for (i=0; i < a.length; i++) {
			if (typeof a[i] == "object" || typeof a[i] == "function") {
				if (typeof a[i].__exceptSeen__ == "undefined") {
					num = 1<<power++;
					a[i].__exceptSeen__ = num;
					bitStrs[0] |= num;
					unique[num] = a[i];
				} else {
					bitStrs[0] |= a[i].__exceptSeen__;
				}
			} else if (typeof seen[a[i]] == "undefined") {
				num = 1<<power++;

				seen[a[i]] = num;

				bitStrs[0] |= num;
				unique[num] = a[i];
			} else {
				bitStrs[0] |= seen[a[i]];
			}
		}
		
		for (i=0; i < b.length; i++) {
			if (typeof b[i] == "object" || typeof b[i] == "function") {
				if (typeof b[i].__exceptSeen__ != "undefined") {
					bitStrs[1] |= b[i].__exceptSeen__;
				}
			} else if (typeof seen[b[i]] != "undefined") {
				bitStrs[1] |= seen[b[i]];
			}
		}

		bitStrs[2] = bitStrs[0] & (~bitStrs[1]);

		var mask = 1;

		while (mask <= bitStrs[2]) {
			if (bitStrs[2] & mask) {
				output[output.length] = unique[bitStrs[2] & mask];
			}
			mask = mask << 1;
		}

		for (var key in unique) {
			if (
				unique.hasOwnProperty(key) && (
					typeof unique[key] == "object" || 
					typeof unique[key] == "function"
				)
			) {
				delete unique[key].__exceptSeen__;
			}
		}

		return output;
	};
} else {
	throw new Error("Static method Array.except already exists.");
}

if (typeof(Array.union) == "undefined") {
	/**
		@interface {
			description: 
				"Take the union of two arrays containing any combination of item types
		
				This method also takes operands which are not arrays interpreting them
				to be a set consisting of a single item and returning an appropriate
				set.
				
				The algorithm is as follows:
					1. Add unique values from `a'
						Loop through array `a', adding the value to output if it hasn't
						been seen and then mark it as seen by either adding a 
						__unionSeen__ property if its an object or function or by 
						adding it to a `seen' hash.
					2. Add unique values from `b'
						Perform the same steps as for `a'
					3. Remove the __unionSeen__ tags
						Loop through the output array calling `delete' for the 
						__unionSeen__ property if the item is an object or function

				The resulting array order will be as if `a' and `b' had been concatenated
				with duplicate values removed. No sorting is done. 

				This method was chosen to allow union of arrays containing any values 
				regardless of whether they can be compared or not.

				Complexity is O(m+n) where m and n are the sizes of the arrays a and b 
				respectively.
				
				Note that the method used is equivalent to strict equality between 
				objects/functions/arrays.  I.e., two objects/arrays/functions are equal
				iff they are the same instance of Object/Array/Function.",

			parameters: [
				{name: "a", type: "array",
					description: 
						"An array containing any number of items and any combination of types" },

				{name: "b", type: "array",
					description: 
						"An array containing any number of items and any combination of types" } ]

			returns: { type: "array",
				description: 
					"An array containing the unique items from both arrays.  The order will 
					be as if the arrays were concatenated with duplicate values removed." }
		}
	*/
	Array.union = function union(a,b) {
		var aIsArr = a instanceof Array, bIsArr = b instanceof Array, i;

		if (!aIsArr && !bIsArr) { return a === b ? [a] : [a,b]; }
		if (!aIsArr) { a = [a]; }
		if (!bIsArr) { b = [b]; }

		var seen = {}, output = [];

		for (i=0; i < a.length; i++) {
			if (typeof a[i] == "object" || typeof a[i] == "function") {
				if (typeof a[i].__unionSeen__ == "undefined") {
					a[i].__unionSeen__ = true;
					output[output.length] = a[i];
				}
			} else if (typeof seen[a[i]] == "undefined") {
				seen[a[i]] = true;
				output[output.length] = a[i];
			}
		}

		for (i=0; i < b.length; i++) {
			if (typeof b[i] == "object" || typeof b[i] == "function") {
				if (typeof b[i].__unionSeen__ == "undefined") {
					b[i].__unionSeen__ = true;
					output[output.length] = b[i];
				}
			} else if (typeof seen[b[i]] == "undefined") {
				seen[b[i]] = true;
				output[output.length] = b[i];
			}
		}

		for (var key in output) {
			if (
				typeof output[key] == "object" || 
				typeof output[key] == "function"
			) {
				delete output[key].__unionSeen__;
			}
		}

		return output;
	};
} else {
	throw new Error("Static method Array.union already exists.");
}

if (typeof(Array.intersect) == "undefined") {
	/**
		@interface {
			description: 
				"Take the intersection of two arrays containing any combination of item types

				This method also takes operands which are not arrays interpreting them
				to be a set consisting of a single item and returning an appropriate set.
		
				The algorithm is as follows:
					1. Find unique items
						Tag each unique item with p, a unique power of 2.
					2. Create bit sets 
						create a bit set for each array `a' and `b' by or-ing the powers, p, 
						of each item together.
					3. Intersect the bit sets
						and the two bit sets together.
					4. Translate the bit set intersection into the corresponding items
						for each bit which is 1 in the resulting set add the corresponding
						item to the output array.
					5. Remove the unique tags
					6. Return the output array
		
				Steps 1 and 2 are performed as follows
					The code loops through each array in turn. During each loop an item is 
					either tagged with __isectSeen__, if it is an object or function, or is 
					added to the `seen' hash if it is a primitive.

					In either case the power of two corresponding to the item is or-d with 
					the bit set created for the array the item belongs to.
		
				Complexity is O(m+n) where m and n are the sizes of arrays a and b 
				respectively.
				
				Note that the method used is equivalent to strict equality between 
				objects/functions/arrays.  I.e., two objects/arrays/functions are equal iff
				they are the same instance of Object/Array/Function.",

			parameters: [
				{name: "a", type: "any",
					description: 
						"An array containing any number of items and any combination of types,
						or a single value to be interpreted as an array containing only that
						value." },

				{name: "b", type: "any",
					description: 
						"An array containing any number of items and any combination of types,
						or a single value to be interpreted as an array containing only that
						value." } ]

			returns: { type: "array",
				description: 
					"An array containing all those elements present in both arrays.
					if no elements are present in both the result will be an empty
					array. The order of the elements will be as if a and b had been
					concatenated with elements not occuring in both arrays and duplicates 
					removed." }
		}
	*/
	Array.intersect = function intersect(a,b) {
		var aIsArr = a instanceof Array, bIsArr = b instanceof Array, i;

		if (!aIsArr && !bIsArr) { return a === b ? [a] : []; }
		if (!aIsArr) { a = [a]; }
		if (!bIsArr) { b = [b]; }

		var unique = {}, seen = {}, bitStrs = [],
			output = [], power = 0, num;

		bitStrs[0] = 0;
		bitStrs[1] = 0;

		for (i=0; i < a.length; i++) {
			if (typeof a[i] == "object" || typeof a[i] == "function") {
				if (typeof a[i].__isectSeen__ == "undefined") {
					num = 1<<power++;
					a[i].__isectSeen__ = num;
					bitStrs[0] |= num;
					unique[num] = a[i];
				} else {
					bitStrs[0] |= a[i].__isectSeen__;
				}
			} else if (typeof seen[a[i]] == "undefined") {
				num = 1<<power++;

				seen[a[i]] = num;

				bitStrs[0] |= num;
				unique[num] = a[i];
			} else {
				bitStrs[0] |= seen[a[i]];
			}
		}

		for (i=0; i < b.length; i++) {
			if (typeof b[i] == "object" || typeof b[i] == "function") {
				if (typeof b[i].__isectSeen__ == "undefined") {
					num = 1<<power++;
					b[i].__isectSeen__ = num;
					bitStrs[1] |= num;
					unique[num] = b[i];
				} else {
					bitStrs[1] |= b[i].__isectSeen__;
				}
			} else if (typeof seen[b[i]] == "undefined") {
				num = 1<<power++;

				seen[b[i]] = num;

				bitStrs[1] |= num;
				unique[num] = b[i];
			} else {
				bitStrs[1] |= seen[b[i]];
			}
		}

		bitStrs[2] = bitStrs[0] & bitStrs[1];

		var mask = 1;

		while (mask <= bitStrs[2]) {
			if (bitStrs[2] & mask) {
				output[output.length] = unique[bitStrs[2] & mask];
			}
			mask = mask << 1;
		}

		for (var key in unique) {
			if (
				typeof unique[key] == "object" || 
				typeof unique[key] == "function"
			) {
				delete unique[key].__isectSeen__;
			}
		}

		return output;
	};
} else {
	throw new Error("Static method Array.intersect already exists.");
}

if (typeof(Array.contains) == "undefined") {
	/**
		@interface {
			description: 
				"Takes the intersection of `a' and `b' and returns true if the result array
				is non-empty. 

				Each argument may be a non-array in which case a new array containing only
				that value will be created and the intersection will be performed using that
				array.",

			parameters: [
				{name: "a", type: "any",
					description: 
						"An array containing any number of items and any combination of types,
						or a single value to be interpreted as an array containing only that 
						value." },

				{name: "b", type: "any",
					description: 
						"An array containing any number of items and any combination of types,
						or a single value to be interpreted as an array containing only that
						value." } ]

			returns: { type: "boolean",
				description: 
					"`true' if any value in `a' also exists in `b', false otherwise.  This uses
					strict equality for objects/arrays/functions.  I.e., two 
					objects/arrays/functions are equal iff they are the same instance of
					Object/Array/Function." }
		}
	*/
	Array.contains = function contains(a, b) {
		return Array.intersect(a,b).length !== 0;
	};
} else {
	throw new Error("Static method Array.contains already exists.");
}
